#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include <linux/futex.h>
#include <sys/time.h>
#include <sys/syscall.h>
#include <sys/types.h>
#include <limits.h>
#include <math.h>

/* Numero de vezes que uma thread deve entrar na regiao critica. */
#define VEZES 4
#define SLP_T 1  /* Tempo de sleep */
#define TODOS LONG_MAX
#define DEBUG 0
#define ERRO 0

typedef struct duelo
{
   int lock;
   short interesse[2];
   int ultimo;
} duelo;

/* resultado dos duelos */
volatile duelo *esp;

/* recurso compartilhado */
volatile int s;

/* numero de rounds - apenas leitura */
int rodada_max;

/* numero de threads */
int n;

/* Retorna -1 se o futex não bloqueou e 
            0 caso contrário */
int futex_wait(void *addr, int val1) {
  return syscall(SYS_futex, addr, FUTEX_WAIT, 
                 val1, NULL, NULL, 0);
}

/* Retorna o número de threads que foram acordadas */
int futex_wake(void *addr, int n) {
    return syscall(SYS_futex, addr, FUTEX_WAKE, 
                   n, NULL, NULL, 0);
}

void zera_duelo(duelo* d)
{
   d->lock = 0;
   d->ultimo = -1;
   d->interesse[0] = d->interesse[1] = 0;
}

void reseta_duelos()
{
   int i;
   int tam = round(pow(2, ceil(log2(n)))) - 1;
   for (i = 0; i < tam; i++)
   {
      zera_duelo((duelo*)&esp[i]);
   }
}

void* f_thread(void *id)
{
   int p, pp, n_id, i, rodada, j;
   short **enderecos_interesses;
   int **enderecos_locks;

   enderecos_interesses = (short **)malloc(sizeof(short *)*(rodada_max-1));
   enderecos_locks = (int **)malloc(sizeof(int *)*(rodada_max-1));

   for (i = 0; i < VEZES; i++)
   {

      n_id = (int)id;
      rodada = 1;

      /* calcula onde buscar duelo */
      p = round(pow(2, rodada_max-rodada-1)) + n_id/2 - 1;

      /* calcula qual minha posicao dentro do duelo */
      pp = n_id % 2;

      while (rodada < rodada_max)
      {

         /* sleep entre rounds */
         sleep(SLP_T);

         if (DEBUG)
            printf("rodada: %d. Duelando id: %d. Posicao: %d. Pp: %d. Interesse: %d. OutroInteresse: %d\n", rodada, (int)id, p, pp, esp[p].interesse[pp], esp[p].interesse[!pp]);

         /* marco que fui o ultimo e levanto interesse */
         esp[p].ultimo = (int)id;
         esp[p].interesse[pp] = 1;
         enderecos_interesses[rodada-1] = &(esp[p].interesse[pp]);
         enderecos_locks[rodada-1] = &(esp[p].lock);


         /* se eu me interessei por ultimo, mas outro jah tinha interesse */
         if (esp[p].ultimo == (int)id && esp[p].interesse[!pp])
         {
            if (DEBUG)
               printf("rodada: %d. DEVO ESPERAR, id: %d\n", rodada-1, (int)id);

            futex_wait((void*)&(esp[p].lock), 0);       /* perdi, espero acabar partida */
         }

         rodada++;

         /* define novo id */
         n_id /= 2;

         /* calcula onde buscar duelo */
         p = round(pow(2, rodada_max-rodada-1)) + n_id/2 - 1;

         /* calcula qual minha posicao dentro do duelo */
         pp = n_id % 2;
         
         if (DEBUG)
            printf("rodada: %d. Ganhei id: %d. Posicao: %d. Interesse outro: %d\n", rodada-1, (int)id, p, esp[p].interesse[!pp]);

      }

      /* regiao critica */
         
      s = (int)id;
      /* sleep entre atribuicao e impressao */
      sleep(SLP_T);
      printf("Thread %d, s = %d.\n", (int)id, s);
         
      /* coloca 0 em todos os niveis de interesse e acorda threads */
      if (ERRO)
         for(j=0; j<=rodada_max-2; j++)
         {
            *(enderecos_interesses[j]) = 0;
            futex_wake((void*)enderecos_locks[j], TODOS);
            sleep(SLP_T);
         }
      else
         for(j=rodada_max-2; j>=0; j--)
         {
            *(enderecos_interesses[j]) = 0;
            futex_wake((void*)enderecos_locks[j], TODOS);
         }

      /* fim regiao critica */
      /*sleep fora da regicao critica */
      sleep(SLP_T);
   }

   free(enderecos_interesses);
   free(enderecos_locks);
   return NULL;
}


int pega_entrada(char* str)
{
   if (str != NULL)
   {
      n = atoi(str);
   }
   else
   {
      return 0;
   }

   return 1;
}

int main(int argn, char** argv)
{
   pthread_t *thrv;
   int i, tam;

   if (argn < 2 || !pega_entrada(argv[1]))
   {
      printf("Uso: programa N\nN -> numero de threads a executar\nEx.: ./camp 10\n");
      return 0;
   }
                    

   tam = round(pow(2, ceil(log2(n)))) - 1;
   rodada_max =  ceil(log2(n)) + 1;
   
   esp = (duelo*)malloc(sizeof(duelo)*tam);
   thrv = (pthread_t*)malloc(sizeof(pthread_t)*n);   

   reseta_duelos();

   for (i = 0; i < n; i++)
   {
      pthread_create(&thrv[i], NULL, (void*)f_thread, (void*)i);
   }

   for (i = 0; i < n; i++)
   {
      pthread_join(thrv[i], NULL); 
   }

   free((void*)esp);
   free(thrv);
   return 0;
}





